package com.cty.seventeenthDay;

import java.util.HashSet;

/*
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表不存在相交节点，返回 null 。
 * */
public class Q_22 {
    public static void main(String[] args) {
        ListNode AListNode1 = new ListNode(1);
        ListNode AListNode2= new ListNode(2);
        ListNode AListNode3 = new ListNode(3);
        ListNode AListNode4 = new ListNode(4);
        ListNode AListNode5 = new ListNode(5);
        AListNode1.next = AListNode2;
        AListNode2.next = AListNode3;
        AListNode3.next = AListNode4;
        AListNode4.next = AListNode5;
        ListNode BListNode1 = new ListNode(1);
        BListNode1.next = AListNode5;
        ListNode resNode = getIntersectionNode(AListNode1, BListNode1);
        System.out.println(resNode.val);
    }

    //
    /*
    *我的思路 先将一个 链表的节点 遍历存入 哈希表中 再和另一个链表的节点比对
    * 时间复杂度O(n) 空间复杂度O(n)
    * */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> listNodes = new HashSet<>();
        listNodes.add(headA);
        ListNode temp;
        temp = headA;
        while (temp.next != null) {
            temp = temp.next;
            listNodes.add(temp);
        }
        temp = headB;
        if (listNodes.contains(temp)) {
            return temp;
        }
        while (temp.next != null) {
            temp = temp.next;
            if (listNodes.contains(temp)) {
                return temp;
            }
        }
        return null;
    }

    // 力扣官方题解 双指针
    /*
    * 思路:
    *   先判断 两个头节点是否为null(或者其中一方为 null ) 若为null 则两个链表不会相交
    *   定义两个指针 分别从两个链表的头部分别出发 走一样的步数 每走一步 判断两个指针指向的节点是否相等 若相等 则返回
    *   当节点指向链表的最后一个元素还没有返回值时 直接指向另一个链表继续遍历
    * */
    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode tA = headA,tB = headB;
        while (tA != tB) {
            tA = tA == null? headB:tA.next;
            tB = tB == null? headA:tB.next;
        }
        return tA;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
